A goal in communication systems is to transmit and receive signals while utilizing minimal transmission channel bandwidth and keeping the overall error rate below an acceptable threshold. Channel bandwidth is filled by transmitters attempting to send ever more data. Errors occur due to interference and channel limitations which distort the data. Systems transmitting and receiving data include cell phones, personal digital assistants (PDAs), local area networks (LANs), wide area networks (WANs), and the like. Such systems may communicate unit to unit, such as cell phone to cell phone, or may use base stations, dish antennas, satellites, and the like.
Transmitted signals are corrupted in many ways before reaching the intended receiver. Interference from signals sent by other transmission sources, leakage from power lines and wired communication systems and the like will all act to corrupt a desired signal. In general, a wireless transmitter will send the transmission signal out in all directions. This transmitted signal will bounce or reflect off buildings, trees and the like. The portion of a signal that is sent along a path leading directly to receiver will reach that receiver. However, portions of the signal which reflect off a building towards the receiver will also reach the receiver. This latter portion of the signal reaches the receiver at a later time than the first portion of the signal, causing a type of interference known as multipath. These interference sources, and others, make it very difficult for a receiver to receive a transmitted signal with an acceptable degree of accuracy, and will increase the frequency of errors. The rate which errors occur in communication systems is expressed in terms of the number of bits of information transmitted, and is referred to as the bit error rate, or BER.
One conventional method of decreasing a communication system's BER is to assign to each original symbol desired to be sent to a receiver, a series of symbols called chips, which are actually sent. This assignment process is called encoding. The number symbols desired to be sent divided by the number of chips actually sent is known as the coding rate. In other words, the ratio of the encoder input rate to the encoder output rate is the coding rate. The redundancy inherent in this coding will allow the receiver to properly decode the received data even in the presence of errors in the reception of individual chips. The encoded user data is referred to as the code word.
As a simple example, assume in a binary system the symbol 1 is to be sent to a receiver. If the symbol 1 is sent and interference corrupts it such that it looks to the receiver like a 0, an error has occurred. Instead, a system may be used in which the series of chips 101 may be sent instead of the 1, and 010 may be sent for each 0. That is to say, a 1 is encoded as a 101, and a 0 is encoded as a 010. The coding rate for this system is ⅓, since 3 chips are sent for each bit. If 101 is sent, and interference corrupts the 1st chip such that it look to the receiver like a 0, the receiver will receive the series 001. Since 001 is different from 101 by only 1 chip, but is different from 010 by two chips, the receiver can easily assume that a 101, corresponding to a 1, was sent. In this situation, no bit error has occurred, even though there was one chip error.
The disadvantage of such a system is the rate of information moving from transmitter to receiver is cut by ⅓ since every bit sent to the receiver requires the transmission of three chips. In situations where the interference is relatively low, this 3:1 redundancy becomes an unnecessary waste of transmission bandwidth. It is desirable to achieve an optimal compromise wherein the code rate if just sufficient to achieve the BER criteria as specified by the standard being used. For instance, in the above example it may be desirable to send only two chips per bit to the receiver. One method known to be effective in adjusting the code rate is the use of a puncture mask, wherein selected bits of the code word as defined by the puncture mask are not transmitted. A puncture mask is a binary sequence having the same length as the code word wherein a zero in the puncture mask indicates the bit is not sent, and a one indicates it is sent. On the receiving side, a zero indicates a position where an erasure is to be inserted. An erasure is an indication to the decoder that there is ambiguity about the value of the received bit.
Where a user data series has been encoded, the puncture mask can be used to delete chips in order to make better use of the available bandwidth. For example, if each symbol to be transmitted is encoded as 3 chips, the code rate would be ⅓. Then, if every third chip is removed, the resulting code rate is ½. By having a variety of puncture masks which may be used, a receiver and transmitter may adjust the coding to minimize the wasted bandwidth while keeping the BER below an acceptable threshold.
FIG. 1 shows a conventional use of a puncture mask. The series. Ti 110 is the user data that a transmitter wants to send to a receiver. The series Ti 110 is first encoded into the longer series Wi 120, which is the code word. A puncture mask Pi 130, having the same length in bits as the code word Wi 120 is then used. For each 1 in the puncture mask, the corresponding chip is transmitted. For each 0 in the puncture mask, an erasure, or deletion occurs, and the corresponding chip is not transmitted. These erasures result in a shorter data series Ei 140, which is sent to the receiver.
Ei 140 is sent by the transmitter, and is distorted by interference before it is received. What is actually received is shown as received data Ri 210 in FIG. 2. Once Ri 210 is received by the receiver, the above operation needs to be performed in reverse. Therefore, the receiver must have the same puncture mask Pi 220 available as was used by the transmitter in FIG. 1. FIG. 2 shows a received data series Ri 210, and the puncture mask Pi 220. For each 1 in the puncture mask Pi 220, the corresponding received data chip is seen as received encoded data. For each 0 in the puncture mask Pi 220, an erasure is inserted after the previous chip in the received user data. This results in the received encoded data series Si 230. This received encoded data series Si 230 can then be decoded into the received user data Ui 240, which, if everything went right, is the same as the user data series Ti 110 in FIG. 1.
As seen from the above, the transmitting unit and the receiving unit each need to have access to the puncture mask Pi 220. The length of each puncture mask Pi 220 is the same length as the code word Wi 120 in FIG. 1, which is the same length as the received encoded data series Si 230 in FIG. 2.
Some standards of wireless communication have a variety of puncture masks which may be used. The use of these puncture masks enables the coding rate to be optimized over a wide range of transmission channel conditions. With conventional means of puncturing, the puncture mask is simply stored in a memory. However, simply storing the puncture masks leads to a requirement of a fairly large memory on a VLSI chip designed to implement these wireless standards. It is thus desirable to be able to store this information on the integrated circuit in an efficient manner.